// 2025/3/31
// https://leetcode.cn/problems/partition-equal-subset-sum/description/?envType=study-plan-v2&envId=top-100-liked
// 分割等和子集

class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int n = nums.size(), sum = 0;
            for(auto& e : nums) sum += e;
            if(sum % 2 == 1) return false;
            sum /= 2;
            vector<vector<bool>> bag(n + 1, vector<bool>(sum + 1, false));
            for(int i = 0; i <= n; i++) bag[i][0] = true;
            for(int i = 1; i <= n; i++)
            {
                for(int j = 0; j <= sum; j++)
                {
                    if(j >= nums[i - 1])
                    {
                        bag[i][j] = bag[i - 1][j - nums[i - 1]];
                    }
                    bag[i][j] = (bag[i][j] || bag[i - 1][j]);
                }
            }
            return bag[n][sum];
        }
    };

class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int n = nums.size(), sum = 0;
            for(auto& e : nums) sum += e;
            if(sum % 2 == 1) return false;
            sum /= 2;
            vector<bool> bag(sum + 1, false);
            bag[0] = true;
            for(int i = 0; i < n; i++)
            {
                for(int j = sum; j >= nums[i]; j--)
                {
                    bag[j] = bag[j - nums[i]] || bag[j];
                }
            }
            return bag[sum];
        }
    };